#include "LinkListApp.h"

LinkList create_list(int n)
{
    LinkList head, p;
    int k;
    head = malloc(sizeof(*head));
    if (!head)
    {
        printf("malloc error\n");
        exit(EXIT_FAILURE);
    }
    head->id = 1;
    head->next = head;
    //head记录了下一个节点的信息，我们使用头插法
    for (k = n; k > 1; --k)
    {
        p = malloc(sizeof(*p));
        if (!p)
        {
            printf("malloc error\n");
            exit(EXIT_FAILURE);
        }
        p->id = k;
        p->next = head->next;
        head->next = p;
    }
    return head;
}

void play(LinkList head, int n)
{
    LinkList p, s;
    int c = 0, k;
    p = head;
    c = 1;
    k = n;
    while (k > 1)
    {
        if (c == 2)
        {
            s = p->next;
            p->next = s->next;
            free(s);
            c = 0;
            k--;
        }
        c++;
        p = p->next;
    }
    printf("the winner is %d\n", p->id);
}

void output(LinkList head)
{
    LinkList p = head;
    do
    {
        printf("%4d", p->id);
        p = p->next;
    } while (p != head);
    printf("\n");
}

int main()
{
    LinkList head;
    int n;
    printf("input the number of players:");
    scanf("%d", &n);
    head = create_list(n);
    if (head)
    {
        output(head);
        play(head, n);
    }
    return 0;
}